Group Anagrams || Super Pow

发表于

Group Anagrams

Question

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Analysis

将每个字符串排序后的值作为key。假如当前的table中不存在该key，则插入key值和新建List；假如存在的话，直接插入get得到的List中。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs.length==0)  return new ArrayList<List<String>>();
        HashMap<String,List<String>> table=new HashMap<String,List<String>>();
        for(String tmp:strs){
            char[] strarr=tmp.toCharArray();
            Arrays.sort(strarr);
            String str=String.valueOf(strarr);
            if(!table.containsKey(str)) table.put(str,new ArrayList<String>());
            table.get(str).add(tmp);
        }
        return new ArrayList<List<String>>(table.values());
    }
}

Super Pow

Question

Your task is to calculate a**b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

1
2
3
a = 2
b = [3]
Result: 8

Example2:

1
2
3
a = 2
b = [1,0]
Result: 1024

Analysis

https://discuss.leetcode.com/topic/50489/c-clean-and-short-solution/7

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    private final int num=1337;
    
    public int superPow(int a, int[] b) {
        if(b.length==0)
            return -1;
        int digit=b[b.length-1];
        int[] remain=Arrays.copyOf(b,b.length-1);
        return pow(superPow(a,remain),10)*pow(a,digit)%num;
    }
    
    private int pow(int a, int k){
        a%=num;
        int res=1;
        for(int i=0;i<k;i++){
            res=res*a%num;
        }
        return res;
    }
}